package qsort;

import java.util.Arrays;

/**
 * Created by status200 on 2018/4/4.
 */
public class Qsort {

    public static void main(String[] args) {

        int[] arr = {342,123,57,25,89,46,46,907};

        System.out.println(Arrays.toString(arr));

        qsort(arr);

        System.out.println(Arrays.toString(arr));

    }

    public static void qsort(int[] arr) {
        qsort(arr,0,arr.length - 1);
    }


    private static void qsort(int[] arr, int start, int end) {

        if(start >= end) {
            return;
        }


        int mid = partition(arr,start,end);

        qsort(arr,start,mid);
        qsort(arr,mid+1,end);

    }

    private static int partition(int[] arr, int start, int end) {

        int key = arr[start];
        while(start < end) {
            while(start < end && key <= arr[end]) {
                end--;
            }
            arr[start] = arr[end];

            while(start < end && key >= arr[start]) {
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = key;

        return start;
    }
}
